#include <stdio.h>
#include <stdlib.h>

#define N 8

int count = 0; // 解决方案计数器

// 使用位运算的N皇后解法
void solve(int row, int cols, int diag1, int diag2)       
{
    if (row == N) 
    {
        count++; // 找到一个解决方案
        return;
    }
    
    int available = ~(cols | diag1 | diag2) & ((1 << N) - 1);
    
    while (available) 
    {
        int pos = available & -available; // 获取最低位的1
        available ^= pos; // 移除这个位置
        
        // 递归调用，更新列和对角线的占用情况
        solve(row + 1, 
              cols | pos, 
              (diag1 | pos) << 1, 
              (diag2 | pos) >> 1);
    }
}

// 打印解决方案的函数
void printSolution(int* queens) 
{
    printf("Solution %d:\n", count);
    for (int i = 0; i < N; i++) 
    {
        for (int j = 0; j < N; j++) 
        {
            if (queens[i] == j) 
            {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

// 带打印功能的N皇后解法
void solveWithPrint(int row, int cols, int diag1, int diag2, int* queens) 
{
    if (row == N) 
    {
        count++;
        printSolution(queens);
        return;
    }
    
    int available = ~(cols | diag1 | diag2) & ((1 << N) - 1);
    
    while (available) 
    {
        int pos = available & -available;
        int col = __builtin_ctz(pos); // 计算pos中末尾0的个数（即位置）
        available ^= pos;
        
        queens[row] = col; // 记录皇后位置
        
        solveWithPrint(row + 1, 
                      cols | pos, 
                      (diag1 | pos) << 1, 
                      (diag2 | pos) >> 1,
                      queens);
    }
}

int main() 
{
    printf("Solving %d-Queens problem...\n", N);
    
    // 方法1: 只计数
    count = 0;
    solve(0, 0, 0, 0);
    printf("Number of solutions: %d\n\n", count);
    
    // 方法2: 打印所有解决方案
    count = 0;
    int queens[N]; // 记录每行皇后的列位置
    solveWithPrint(0, 0, 0, 0, queens);
    
    return 0;
}